package com.singzi.algorithm;

import com.singzi.leetcode.obj.TreeNode;

import java.util.HashMap;


public class CreateBT{
    private HashMap<Integer, Integer> indexMap;
    public TreeNode buildTree(int[] preOrder, int[] inOrder){
        indexMap = new HashMap<Integer, Integer>();
        int n = inOrder.length;
        for(int i = 0;i < n;i++){
            indexMap.put(inOrder[i], i);
        }
        return createTree(preOrder, inOrder,0,n-1, 0, n-1);




    }
    public TreeNode createTree(int[] preOrder, int[] inOrder, int preLeft, int preRight, int midLeft, int midRight){

        if(preLeft > preRight) return null;
        int indexIn = indexMap.get(preOrder[preLeft]);

        TreeNode root = new TreeNode(preOrder[preLeft]);
        root.left = createTree(preOrder, inOrder, preLeft+1, preLeft+indexIn-midLeft, midLeft,indexIn-1);
        root.right = createTree(preOrder, inOrder, preLeft+indexIn-midLeft+1,preRight,indexIn+1,midRight);
        return root;
    }

}
